package com.liang.leetcode.list;

/**
 * 206.反转链表：
 * <a href="https://leetcode.cn/problems/reverse-linked-list/">https://leetcode.cn/problems/reverse-linked-list/</a>
 * 题意：
 * 给你单链表的头结点 head ，请你反转链表，并返回反转后的链表。
 * 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
 */
public class List03_ReverseList {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        ListNode head = ListNodeUtil.createLinkedList(arr); // 初始链表：1 -> 2 -> 3 -> 4 -> 5 -> null
        head = reverseList2(head);
        ListNodeUtil.printLinkedList(head); // 链表变为：5 -> 4 -> 3 -> 2 -> 1 -> null
    }

    /**
     * 方法1：双指针法
     * @param head
     * @return
     */
    public static ListNode reverseList(ListNode head) {
        // 初始化三个指针
        ListNode cur = head;     // 当前结点，最初指向头结点
        ListNode pre = null;     // 前一个结点，最初为 null
        ListNode temp = null;    // 临时结点，用于保存下一个结点

        // 遍历链表直到当前结点为 null
        while (cur != null) {
            // 保存下一结点
            temp = cur.next;
            // 反转当前结点的next结点
            cur.next = pre;
            // 先更新 pre，再更新 cur
            pre = cur;
            cur = temp;
        }
        // 循环结束后，pre 将指向新的头结点（原链表的尾结点）
        return pre;
    }

    /**
     * 方法2：递归
     * @param head
     * @return
     */
    public static ListNode reverseList2(ListNode head) {
        return reverse(null, head);
    }

    public static ListNode reverse(ListNode prev, ListNode cur) {
        // 递归出口
        if (cur == null) {
            // 返回新链表的头结点
            return prev;
        }

        ListNode temp = null; //临时结点
        temp = cur.next; // 先保存下一个结点
        cur.next = prev; // 再反转当前结点cur，指向前一个结点pre

        // 更新prev、cur位置
        // prev = cur;
        // cur = temp;
        return reverse(cur, temp);
    }
}
